package algorithm.dichotomy.leetcode;

/**
 * @author: 柒月
 * @date: 2025/5/1 上午10:54
 * @version: 1.0
 */
public class Problem162 {

    // https://leetcode.cn/problems/find-peak-element/
    /**
     * @param nums 数组不是一个有序数组也可以二分
     * @return 任何一个峰值 所在位置即可
     */
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        // 如果数组长度或者数组中的第一个元素大于第二个元素 说明数组第一个位置就是峰值返回即可
        if (n == 1 || nums[0] > nums[1]) {
            return 0;
        }

        // 如果第n-1个元素大于第n-2个元素 说明数组第n-1个位置就是峰值直接返回即可
        if (nums[n - 1] > nums[n - 2]) {
            return n - 1;
        }

        // 前面已经判断了数组中的0位置和n-1位置不是峰值所有直接从1位置和n-2位置开始判断
        int left = 1, rigth = n - 2, mid;
        while (left <= rigth) {
            // 计算中间值 和 mid=(left+rigth)/2等价 只是这个更安全
            mid = left + ((rigth - left) >> 1);
            // 中间值小于左边的值表示mid位置不是峰值但是因为前面判断l0位置和1位置不是峰值前面的升中间是降说明在[left,mid-1]一定用峰值
            if (nums[mid] < nums[mid - 1]) {
                rigth = mid - 1;
            } else if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}
